package org.example.BinaryTree;

public class Lowest_Common_Ancestor {
    public static TreeNode node = null;

    public static void main(String[] args) {
        //二叉树的最近公共祖先

        //给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
        //百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode root = new TreeNode(0);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;
        node5.left = node7;
        TreeNode treeNode = lowestCommonAncestor(root, node3, node1);
        if (treeNode != null) {
            System.out.println(treeNode.val);
        } else {
            System.out.println("null");
        }

    }

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        search(root, p, q);
        return node;
    }

    public static boolean search(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean left = search(root.left, p, q);
        boolean right = search(root.right, p, q);
        if ((left && right) || ((root.val == p.val || root.val == q.val) && (left || right))) {
            node = root;
            return true;
        }
        if (root.val == p.val || root.val == q.val) return true;
        return left || right;
    }
}
